//
//  HeapSort.java
//  joosVM
//
//  Created by Smári Waage on 24.10.2009.
//  Copyright 2009 smari.org. All rights reserved.
//
package SortingAlgorithms;
public class HeapSortAlgorithm{
	
	
	private static int[] a;
    private static int n;
	
    public static void sort(int[] a0)
    {
        a=a0;
        n=a.length;
        heapsort();
    }
	
    public static void heapsort()
    {
        buildheap();
        while (n>1)
        {
            n--;
            exchange (0, n);
            downheap (0);
        } 
    }
	
    public static void buildheap()
    {
        for (int v=n/2-1; v>=0; v--)
            downheap (v);
    }
	public static void exchange(int i, int j)
    {
        int t=a[i];
        a[i]=a[j];
        a[j]=t;
    }
    private static void downheap(int v)
    {
        int w=2*v+1;    // first descendant of v
        while (w<n)
        {
            if (w+1<n)    // is there a second descendant?
                if (a[w+1]>a[w]) w++;
            // w is the descendant of v with maximum label
			
            //if (!(a[v]>=a[w])){ 
			if (a[v]>=a[w]) return;  // v has heap property
				
            // otherwise
            exchange(v, w);  // exchange labels of v and w
            v=w;        // continue
            w=2*v+1;
			//}
        }
    }
	
    
	
	public static void BetterHeapSort(){
		System.out.println("Better heap sort 1000 items");
		int arr[] = getRandom1000Array();
		sort(arr);
		//for(int i=0;i<arr.length;i++){
		//	System.out.println(arr[i]);
		//}
		//testAssert(arr.length, arr[arr.length-1]);
		System.out.println("\n");
	}

	
	public static void BadHeapSort(){
		int i;
		int arr[] = getRandom100Array();//{3,1,4,5,2,10,7,9,6,8};//getRandom10Array();//
		
		System.out.println("Bad heap sort 100 items");

		
		//sort(arr);
		//for (i = 0; i < arr.length; i++)
		//	System.out.println(arr[i]);
		
		
		for(i=arr.length; i>1; i--){
			fnSortHeap(arr, i - 1);
		}
		
		//for (i = 0; i < arr.length; i++)
		//	System.out.println(arr[i]);
		
		
		System.out.println("\n");
		
	}
	
	public static void main(String a[]){
		BadHeapSort();
		BetterHeapSort();
	}
	
	public static void fnSortHeap(int array[], int arr_ubound){
		//System.out.print("Starting a Sort in index arr_ubound: ");
		//System.out.println(arr_ubound);
		int i, o;
        int lChild, rChild, mChild, root, temp;
		root = (arr_ubound-1)/2;
		//System.out.print("Root ");
		//System.out.println(root);
		
		for(o = root; o >= 0; o--){
			//System.out.print("\tOuter iteration: ");
			//System.out.println(o);
			for(i=root;i>=0;i--){
				lChild = (2*i)+1;
                rChild = (2*i)+2;
				
				//System.out.print("\t\tInner Itr lChild: ");
				//System.out.print(lChild);				   
				//System.out.print(" rChild: ");
				//System.out.print(rChild);
				//System.out.print(" mChild: ");
				
								   
				if((lChild <= arr_ubound) && (rChild <= arr_ubound)){
					if(array[rChild] >= array[lChild]){
						mChild = rChild;
					}else{
						mChild = lChild;
					}
					
				}else{
					if(rChild > arr_ubound){
						mChild = lChild;
					}else{
						mChild = rChild;
					}
				}
				//System.out.print(mChild);
				//System.out.print(" if: ");
				//System.out.print(array[i]);
				//System.out.print(" <: ");
				//System.out.println(array[mChild]);
				if(array[i] < array[mChild]){
					//System.out.print("\t\t\tSwaping idx:");
					//System.out.print(i);
					//System.out.print(" value:");
					//System.out.print(array[i]);
					//System.out.print(" with idx:");
					//System.out.print(mChild);
					//System.out.print(" value:");
					//System.out.println(array[mChild]);
					
					temp = array[i];
					array[i] = array[mChild];
                    array[mChild] = temp;
				}
				
			}
			
		}
		
		temp = array[0];
		array[0] = array[arr_ubound];
		array[arr_ubound] = temp;
		//System.out.print("End swap: ");
		//System.out.print(array[0]);
		//System.out.print(" with: ");
		//System.out.println(array[arr_ubound]);
		
		return;
	}
	public static int[] getRandom10Array(){
		int arr[] = {
			9,
			3,
			4,
			5,
			2,
			10,
			8,
			7,
			6,
			10};
		return arr;
		
	}
	public static int[] getRandom100Array(){
		
		int arr[] = {
			8,
			89,
			6,
			46,
			38,
			11,
			10,
			37,
			28,
			3,
			4,
			51,
			43,
			12,
			78,
			62,
			16,
			22,
			19,
			41,
			53,
			18,
			20,
			73,
			21,
			97,
			86,
			58,
			80,
			85,
			45,
			52,
			76,
			96,
			26,
			81,
			36,
			15,
			2,
			48,
			90,
			14,
			99,
			79,
			29,
			32,
			87,
			93,
			60,
			67,
			77,
			65,
			40,
			30,
			9,
			84,
			91,
			25,
			82,
			5,
			94,
			75,
			23,
			95,
			27,
			54,
			72,
			66,
			83,
			49,
			33,
			56,
			17,
			44,
			59,
			61,
			74,
			100,
			31,
			98,
			13,
			64,
			34,
			7,
			71,
			63,
			24,
			39,
			92,
			42,
			1,
			50,
			88,
			55,
			70,
			69,
			35,
			57,
			68,
			47};
		return arr;
	}
	
	public static int[] getRandom1000Array(){
		
		int arr[] = {
		502,
		96,
		721,
		171,
		913,
		949,
		559,
		42,
		927,
		908,
		327,
		462,
		766,
		372,
		376,
		580,
		205,
		641,
		847,
		926,
		664,
		911,
		438,
		124,
		767,
		567,
		856,
		574,
		751,
		30,
		982,
		600,
		345,
		676,
		623,
		553,
		948,
		494,
		762,
		947,
		890,
		74,
		839,
		880,
		916,
		838,
		422,
		367,
		459,
		903,
		241,
		962,
		113,
		126,
		54,
		834,
		718,
		579,
		752,
		822,
		833,
		760,
		125,
		295,
		63,
		396,
		463,
		348,
		223,
		922,
		683,
		172,
		242,
		886,
		689,
		375,
		250,
		91,
		609,
		798,
		254,
		592,
		521,
		701,
		665,
		753,
		953,
		455,
		167,
		972,
		181,
		106,
		69,
		409,
		923,
		820,
		354,
		774,
		649,
		805,
		282,
		394,
		961,
		936,
		984,
		266,
		795,
		989,
		577,
		997,
		797,
		659,
		696,
		289,
		974,
		671,
		358,
		99,
		991,
		344,
		653,
		968,
		150,
		503,
		252,
		75,
		251,
		990,
		155,
		449,
		442,
		362,
		300,
		6,
		132,
		958,
		232,
		279,
		484,
		184,
		608,
		109,
		304,
		583,
		168,
		467,
		296,
		221,
		575,
		979,
		98,
		860,
		148,
		647,
		466,
		378,
		488,
		626,
		200,
		523,
		576,
		337,
		831,
		662,
		186,
		976,
		686,
		325,
		292,
		78,
		771,
		260,
		18,
		790,
		490,
		9,
		720,
		928,
		15,
		256,
		53,
		985,
		382,
		469,
		733,
		16,
		954,
		120,
		602,
		66,
		675,
		883,
		131,
		302,
		338,
		827,
		620,
		310,
		616,
		988,
		229,
		722,
		869,
		809,
		713,
		309,
		811,
		258,
		492,
		692,
		957,
		368,
		188,
		140,
		994,
		202,
		599,
		217,
		384,
		895,
		950,
		198,
		173,
		230,
		857,
		941,
		757,
		143,
		846,
		476,
		802,
		470,
		816,
		791,
		49,
		967,
		392,
		844,
		755,
		399,
		14,
		203,
		714,
		419,
		20,
		630,
		47,
		210,
		646,
		582,
		285,
		287,
		460,
		174,
		335,
		166,
		387,
		489,
		236,
		485,
		294,
		996,
		62,
		629,
		871,
		190,
		782,
		525,
		169,
		770,
		385,
		320,
		832,
		391,
		889,
		917,
		591,
		51,
		924,
		45,
		56,
		999,
		84,
		952,
		615,
		730,
		182,
		564,
		637,
		690,
		276,
		884,
		536,
		776,
		566,
		111,
		660,
		909,
		134,
		612,
		792,
		94,
		436,
		479,
		808,
		537,
		622,
		133,
		37,
		308,
		636,
		206,
		511,
		40,
		360,
		364,
		885,
		288,
		60,
		530,
		986,
		654,
		248,
		873,
		373,
		763,
		277,
		929,
		670,
		224,
		981,
		764,
		187,
		55,
		146,
		727,
		233,
		157,
		563,
		759,
		420,
		535,
		633,
		80,
		527,
		517,
		397,
		603,
		516,
		964,
		588,
		852,
		39,
		893,
		959,
		841,
		32,
		864,
		398,
		402,
		617,
		715,
		734,
		925,
		446,
		824,
		34,
		433,
		164,
		393,
		240,
		861,
		347,
		218,
		568,
		632,
		765,
		404,
		992,
		237,
		882,
		691,
		196,
		220,
		818,
		853,
		318,
		447,
		679,
		321,
		639,
		482,
		453,
		274,
		349,
		970,
		868,
		161,
		651,
		493,
		643,
		50,
		1,
		585,
		379,
		208,
		483,
		149,
		830,
		346,
		914,
		197,
		794,
		246,
		499,
		902,
		572,
		330,
		934,
		381,
		407,
		267,
		510,
		610,
		598,
		551,
		638,
		673,
		742,
		781,
		849,
		621,
		661,
		383,
		644,
			255,
			835,
			769,
			897,
			807,
			497,
		746,
		680,
		272,
		829,
		548,
		315,
		777,
		655,
		361,
		870,
			562,
			874,
			234,
			412,
			199,
			8,
		712,
		44,
		905,
		357,
		500,
		634,
		938,
		862,
		319,
		946,
			478,
			429,
			374,
			334,
			97,
			386,
		524,
		352,
		951,
		434,
		225,
		601,
		26,
		561,
		594,
		584,
			740,
			851,
			117,
			415,
			423,
			743,
		52,
		83,
		758,
		933,
		472,
		498,
		405,
		162,
		578,
		231,
			306,
			3,
			228,
			301,
			262,
			356,
		682,
		628,
		891,
		183,
		656,
		779,
		21,
		540,
		450,
		878,
			464,
			95,
			76,
			270,
			867,
			247,
		699,
		454,
		281,
		284,
		477,
		894,
		554,
		209,
		339,
		77,
		33,
			787,
			176,
			613,
			291,
			465,
			931,
		549,
		418,
		458,
		850,
		158,
		175,
		842,
		36,
		58,
		371,
			312,
			380,
			697,
			543,
			778,
			748,
		843,
		717,
		46,
		710,
		253,
		604,
		13,
		73,
		556,
		596,
			708,
			5,
			955,
			413,
			772,
			340,
		705,
		411,
		545,
		589,
		263,
		627,
		163,
		552,
		980,
		975,
			324,
			193,
			896,
			103,
			745,
			88,
		738,
		451,
		910,
		154,
		491,
		159,
		522,
		245,
		768,
		311,
			800,
			942,
			546,
			783,
			716,
			7,
		912,
		215,
		518,
		587,
		544,
		322,
		314,
		569,
		515,
		573,
			658,
			724,
			444,
			87,
			904,
			195,
		747,
		147,
		631,
		239,
		558,
		735,
		813,
		38,
		586,
		866,
			725,
			892,
			810,
			317,
			135,
			22,
		987,
		700,
		814,
		667,
		207,
		440,
		899,
		4,
		2,
		212,
			593,
			359,
			179,
			657,
			269,
			668,
		107,
		848,
		12,
		597,
		93,
		519,
		201,
		332,
		437,
		761,
		90,
		92,
			611,
			542,
			257,
			865,
			249,
			64,
		648,
		313,
		377,
		565,
		264,
		443,
		452,
		43,
		642,
		72,
			185,
			151,
			788,
			541,
			481,
			139,
		605,
		138,
		532,
		749,
		112,
		775,
		213,
		786,
		520,
		698,
			110,
			973,
			773,
			19,
			993,
			468,
		286,
		145,
		369,
		590,
		971,
		128,
		739,
		439,
		581,
		293,
			678,
			687,
			966,
			299,
			920,
			406,
		528,
		732,
		473,
		674,
		921,
		487,
		61,
		265,
		995,
		216,
		85,
			677,
			425,
			825,
			887,
			879,
			273,
		486,
		693,
		127,
		403,
		401,
		840,
		10,
		823,
		512,
		694,
			939,
			353,
			29,
			606,
			280,
			501,
		709,
		956,
		178,
		424,
		41,
		754,
		365,
		571,
		821,
		194,
			116,
			618,
			388,
			875,
			619,
			214,
		550,
		57,
		703,
		259,
		901,
		685,
		82,
		801,
		803,
		607,
			192,
			513,
			475,
			877,
			940,
			456,
		533,
		737,
		828,
		238,
		59,
		67,
		123,
		326,
		86,
		736,
			547,
			663,
			555,
			428,
			504,
			702,
		538,
		370,
		495,
		333,
		268,
		854,
		235,
		514,
		729,
		219,
			153,
			480,
			152,
			119,
			316,
			89,
		328,
		858,
		785,
		426,
		872,
		471,
		108,
		915,
		156,
		804,
			793,
			672,
			25,
			531,
			421,
			432,
		635,
		750,
		445,
		65,
		756,
		557,
		105,
		165,
		298,
		998,
			461,
			836,
			28,
			290,
			170,
			363,
		11,
		278,
		23,
		539,
		943,
		744,
		191,
		799,
		624,
		100,
			855,
			211,
			507,
			965,
			160,
			227,
		204,
		189,
		508,
		688,
		121,
		448,
		142,
		707,
		307,
		297,
			650,
			115,
			907,
			731,
			31,
			728,
		129,
		222,
		351,
		726,
		17,
		81,
		723,
		342,
		136,
		137,
			935,
			226,
			796,
			79,
			570,
			509,
		457,
		35,
		815,
		945,
		400,
		331,
		681,
		496,
		24,
		944,
			898,
			329,
			68,
			395,
			144,
			101,
		863,
		71,
		560,
		932,
		431,
		414,
		102,
		122,
		303,
		355,
			427,
			669,
			366,
			640,
			529,
			323,
		526,
		244,
		876,
		341,
		283,
		859,
		177,
		937,
		343,
		881,
			271,
			819,
			130,
			918,
			969,
			625,
		845,
		408,
		118,
		350,
		652,
		474,
		812,
		963,
		70,
		336,
			977,
			983,
			141,
			441,
			305,
			666,
		780,
		275,
		48,
		645,
		506,
		930,
		114,
		789,
		505,
		826,
			837,
			719,
			614,
			416,
			104,
			27,
		430,
		243,
		1000,
		417,
		900,
		960,
		704,
		595,
		534,
		261,
			711,
			410,
			435,
			888,
			741,
			817,
		978,
		784,
		695,
		389,
		919,
		906,
		684,
		180,
		806,
		390,
		706};
	
		return arr;
	}

}

